package leetcode.array;

import java.util.Random;

/**
 * @Description: https://leetcode.cn/problems/kth-largest-element-in-an-array/
 * @Author Ammar
 * @Create 2023/8/4 13:12
 */
public class _215_数组中的第K个最大元素 {
    int[] nums;

    public void swap(int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    public int partition(int left, int right, int pivot_index) {
        int pivot = nums[pivot_index];
        swap(pivot_index, right);
        int store_index = left;
        for (int i = left; i <= right; i++) {
            if (nums[i] < pivot) {
                swap(store_index, i);
                store_index++;
            }
        }
        swap(store_index, right);
        return store_index;
    }

    public int quickselect(int left, int right, int k_smallest) {
        if (left == right) return nums[left];
        Random random_num = new Random();
        int pivot_index = left + random_num.nextInt(right - left);
        pivot_index = partition(left, right, pivot_index);
        if (k_smallest == pivot_index) return nums[k_smallest];
        else if (k_smallest < pivot_index) return quickselect(left, pivot_index - 1, k_smallest);

        return quickselect(pivot_index + 1, right, k_smallest);
    }

    /**
     * 基于快速排序的选择选择方法，时间复杂度为 O(n)
     */
    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        int n = nums.length;
        return quickselect(0, n - 1, n - k);
    }
}
